1. Field of the Invention
This invention relates generally to manufacturing systems and assembly lines, and more particularly, to methods and apparatus for designing and controlling the operation of flexible manufacturing systems and assembly lines.
2. Description of the Related Art
Some structures and concepts that are useful for describing manufacturing systems are defined as follows:
Work pieces are objects and materials that are changed and combined to make a finished product; PA1 Jobs are operations that change or combine the work pieces; PA1 Resources are machines, humans with tools, fixtures, transport devices, and buffers that perform the jobs on the work pieces; PA1 Assembly line is a circuit that the work pieces follow between the resources that perform the jobs; PA1 Workcell is a physical portion of the manufacturing system; and PA1 Flexible manufacturing systems (FMS) are assembly lines or workcells, wherein the timing of the jobs or assignment of the resources is flexible.
The design and operation of a workcell involves two steps. First, decisions are made on the sequencing of jobs to be performed on individual work pieces. Normally, the job sequence is based on, at least, some considerations external to the form of the workcell. Second, decisions are made on the control of the workcell that will perform the predetermined job sequence. These control decisions involve the assignments of particular resources to the jobs of the predetermined sequence. The control decisions entail starting jobs and releasing resources when jobs are done. The control decisions may also entail choosing among different resource assignment possibilities when several resources can perform a job, and resolving priorities when several jobs are simultaneously assigned to the same resource.
FIG. 1 shows a simple workcell 6 whose operation involves such control decisions. Work pieces 8 follow a fixed circuit 10 from an input 12 for raw work pieces 14 to an output 16 for finished products 18. At the input 12, the raw work pieces 14 are attached to pallets 20 that facilitate handling. The pallets 20 are removed from the finished products 18 at the output 16 and automatically returned to the input 12. First and second machines 22, 26 perform jobs. For example, the first and second machines 22, 26 may drill holes and cut the work pieces 8, respectively. The input of the second machine 26 is a buffer 24 that can hold up to two work pieces 8 simultaneously. The raw work pieces 14 are moved automatically from the input 12 to the first machine 22, and from the buffer 24 to the second machine 26 by conveyers 28, 30. A robot arm 32 transports the work pieces 8 from the first machine 22 to the buffer 24 and from the second machine 26 to the output 16. The resources of the workcell 6 of FIG. 1 are the first and second machines 22, 26, the buffer 24, the robot arm 32 and the pallets 20.
Though the illustrative workcell 6 of FIG. 1 is simple, its operation involves non-trivial control decisions. First, the robot arm 32 performs several jobs 34, 36. The first job 34 is to transport the work pieces 8 from the first machine 22 to the buffer 24, and the second job 36 is to transport the work piece 8 from the second machine 26 to the output 16. The first and second jobs 34, 36 of the robot arm 32 are mutually exclusive, i.e. cannot be performed simultaneously. Thus, the operation of the robot arm 32 can encounter conflict situations where both the first and second jobs are requested simultaneously. Second, the buffer 24 and pallets 20 are resources in multiple copies. The buffer 24 has two spaces 38 for holding the work pieces 8, and there are several pallets 20. Multiple copies complicate controlling the assignment of the resources to the jobs. The multiple job and multiple copy resources introduce flexibility into the control decisions and make the workcell 6 of FIG. 1 a FMS.
A FMS is a discrete event (DE) system. DE systems are defined by a set of event-states and transitions between the event-states. In the workcell of a manufacturing system, the event-states are the states of the resources, i.e., rest states and job performance states, the inputs for raw work pieces and outputs for finished products. The transitions are the acts of starting and stopping resources, i.e., transitions from rest states to job performance states and vice versa. The transitions involve the substantially simultaneous movement of the work pieces between inputs, resources, and outputs. The event-states and transitions of the DE system can be represented by a directed graph or Petri net (PN). In the PN, the event-states and transitions are represented by circles and vertical lines respectively. Directed lines indicate the transitions of the work pieces and of the resources between the event-states. The event-states and transitions alternate along the directed lines of the PN. While the resources of the workcell occupy two types of event-states, rest event-states and job event-states, the work pieces only occupy the job event-states, inputs or outputs.
FIG. 2 is the PN of the FMS of FIG. 1. The job event-states of the first machine 40, buffer 42, and second machine 44 lie along a straight line 46 representing the circuit of work pieces 8 of FIG. 1. The robot arm 32 has both first and second job event-states 48, 50 along the same straight line 46. The rest event-states of the first machine 52, buffer 54, second machine 56, and robot arm 58 are off the circuit 46 of work pieces 8. The job event-states of the pallets are the job event-states of the other resources 40, 42, 44, 48, 50, because the work pieces 8 are attached to the pallets 20 while moving along the circuit 46. The pallets have a rest event-state 60 between the first transition x1 after the input event-state 62 and the last transition x6 before the output event-state 64. At these two transitions x1, x6, the pallets 20 are attached and removed respectively from the work pieces 8.
In a PN, the time dependent occupation of the event-states by resources is indicated by marking the circles representing the event-state with dots. At the time represented by FIG. 2, the workcell 6 of FIG. 1 has four pallets 60, one first machine 52, two buffer spaces 54, one robot arm 58, and one second machine 56 occupying rest event-states 60, 52, 54, 58, 56. At the same time, there is one raw work piece 14 of FIG. 1 at the input event-state 62. The work pieces 14 make transitions x1-x6 between job event-states along the directed circuit 46. The pallets 20 of FIG. 1 make transitions between different job event-states x2-x5 except for transitions x1, x6 at the input 62 and output 64, which are transitions between rest and job event-states 60, 40, 50. The other resources only make transitions between job and rest event-states. Time dependent transitions between event-states ordinarily change the markings, e.g., occupations, of the circles of the PN.
Since PN's faithfully represent all event-states, the prior art has employed PN's to the design and to analyze the operation of FMS's. The prior art use of PN's to design controllers of workcells had limitations. First, the analysis of practical FMS's through PN's is complicated. For designing automated controllers, simpler techniques are preferable. Second, the PN technique requires a separate graph to represent each time state of the workcell. Thus, PN's do not present a straightforward method for analyzing the time evolution of the workcell. Automated controllers cannot simply determine from a PN how to operate the workcell. Third, the prior art based the design and control of PN's on "top-down" and "bottom-up" designs by using rules such as series mutual exclusion, parallel mutual exclusion, and forbidden states of resource allocation. These rules do not guarantee that a global evolution is operative, i.e. absence of deadlock. In the prior art, PN design was supplemented with simulations to insure that the workcell would not evolve into an inoperative or deadlocked state.
Though the prior art has been illustrated by the simple example of FIGS. 1-2, the difficulties of constructing simple rules for controller operation ordinarily reappear in more complex FMS's. To operate controllers of FMS's in an automated mode, it would be useful to have a more straightforward representation for the time evolution of workcell.
The present invention is directed to overcoming, or at least reducing the effects of, one or more of the problems set forth above.